//
//  Problem5.swift
//  LeetCode
//
//  Created by zhulongiMac02 on 2019/11/27.
//  Copyright © 2019 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 5 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

 示例 1：

 输入: "babad"
 输出: "bab"
 注意: "aba" 也是一个有效答案。
 示例 2：

 输入: "cbbd"
 输出: "bb"

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Problem5: NSObject {
    func solution() {
        // 测试用例：
        let str = "babad"
        let str1 = "abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa"
        let strReplyA = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
        let strReplyB = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
        //        let str = "cbbd"
        let strMaxTime = "jglknendplocymmvwtoxvebkekzfdhykknufqdkntnqvgfbahsljkobhbxkvyictzkqjqydczuxjkgecdyhixdttxfqmgksrkyvopwprsgoszftuhawflzjyuyrujrxluhzjvbflxgcovilthvuihzttzithnsqbdxtafxrfrblulsakrahulwthhbjcslceewxfxtavljpimaqqlcbrdgtgjryjytgxljxtravwdlnrrauxplempnbfeusgtqzjtzshwieutxdytlrrqvyemlyzolhbkzhyfyttevqnfvmpqjngcnazmaagwihxrhmcibyfkccyrqwnzlzqeuenhwlzhbxqxerfifzncimwqsfatudjihtumrtjtggzleovihifxufvwqeimbxvzlxwcsknksogsbwwdlwulnetdysvsfkonggeedtshxqkgbhoscjgpiel" // sknks
        
        print("max = '", isLongestPalindrome3(strMaxTime), "'")
    }
    
    // 判断s是否是回文
    func isPalindromic(_ s: String) -> Bool {
        print(s)
        var start = s.startIndex
        var end = s.index(before: s.endIndex)
        while start < end {
            if s[start] != s[end]{
                return false
            }
            start = s.index(after: start)
            end = s.index(before: end)
        }
        return true
    }
    
    
    
    // 第一种方法：暴力破解法1.0, 获取所有的字串，然后判断是否是回文
    // 时间复杂度：两层 for 循环 O(n²）O(n²），for 循环里边判断是否为回文 O(n）O(n），所以时间复杂度为 O(n³）O(n³）。
    // 空间复杂度：O(1）O(1），常数个变量。
    // 结果：超时，执行strMaxTime，使用了1028 ms
    func isLongestPalindrome(_ s: String) -> String {
        if s.count < 2 {
            return s
        }
        
        var i = s.startIndex
        var j = s.index(after: i)
        
        print(i.encodedOffset, j.encodedOffset)
        var maxString: String = String(s[i])
        
        while i < s.endIndex {
            while j < s.endIndex {
                let str = s[i...j]              // 执行了997次
                if str.count > maxString.count, isPalindromic(String(str)) == true {
                    maxString = String(str)
                }
                if i.encodedOffset + maxString.count + 1 > s.count {
                    break
                }
                j = s.index(after: j)           // 执行了996次
            }
            
            if i.encodedOffset + maxString.count + 1 > s.count {
                break
            }
            j = s.index(i, offsetBy: maxString.count + 1)
            i = s.index(after: i)
        }
        
        return maxString
    }
    
    // 第二种方法：获取第一个字符在字符串中对应的字符，然后判断这个是否是回文
    // 结果：超时，执行strReplyA，使用了6556 ms, 放弃
    func isLongestPalindrome1(_ s: String) -> String {
        if s.count < 2 {
            return s
        }
        
        var i = s.startIndex
        var j = s.index(after: i)
        var maxString: String = String(s[i])
        
        while i < s.endIndex {
            if i.encodedOffset + maxString.count > s.count {
                break;
            }
            let curMaxIndex = s.index(i, offsetBy: maxString.count)
            let left = j >= curMaxIndex ? j : curMaxIndex
            if left < s.endIndex, let index = s[left...s.index(before: s.endIndex)].index(of: s[i]) {
                if (index.encodedOffset - i.encodedOffset) > maxString.count - 1 {
                    if isPalindromic(String(s[i...index])) == true {
                        maxString = String(s[i...index])
                    }
                    if index >= s.endIndex {
                        break;
                    }
                    j = s.index(after: index)
                } else {
                    if curMaxIndex >= s.endIndex {
                        break;
                    }
                    j = s.index(after: curMaxIndex)
                }
            } else {
                i = s.index(after: i)
                if i < s.endIndex {
                    j = s.index(after: i)
                } else {
                    break
                }
            }
        }
        
        return maxString
    }
    
    // 第三种方法：P(i,j)=(P(i+1,j−1)&&S[i]==S[j])
    // 结果：strMaxTime: 12ms；strReplyA: 1152 ms; strReplyB: 4660 ms 超时
    func isLongestPalindrome3(_ s: String) -> String {
        if s.count < 2 {
            return s
        }
        
        var i = s.index(before: s.endIndex)
        
        var maxString: String = ""
        var P :[Bool] = Array.init(repeating: true, count: s.count)
        while i >= s.startIndex {
            var j = s.index(before: s.endIndex)
            while j >= i {
                
                P[j.encodedOffset] =  s[i] == s[j] && (j.encodedOffset - i.encodedOffset < 3 || P[j.encodedOffset - 1])
                if P[j.encodedOffset], j.encodedOffset - i.encodedOffset + 1 > maxString.count {
                    //                    if i == j {
                    //                        maxString = String(s[i])
                    //                    } else {
                    //                        maxString = String(s[i...j])
                    //                    }
                    maxString = String(s[i...j])
                }
                if j > s.startIndex {
                    j = s.index(before: j)
                } else {
                    break
                }
            }
            
            if i > s.startIndex {
                i = s.index(before: i)
            } else {
                break
            }
        }
        
        return maxString
    }
    
    func longestPalindrome(_ s: String) -> String {
        if s.count <= 1 {
            return s
        }
        
        var str = ""
        
        var i = s.startIndex;
        while i != s.endIndex {
            var j = s.endIndex
            if s[i..<s.endIndex].count <= str.count {
                return str
            }
            while let range = s.range(of: String(s[i]), options: .backwards, range: s.index(after: i)..<j, locale: nil) {
                if self.countPalindrome(s: s, start: i, end: range.lowerBound) > str.count {
                    str = String(s[i...range.lowerBound])
                    if str.count == s.count {
                        return str
                    }
                }
                j = range.lowerBound
                if s[i...j].count <= str.count {
                    break
                }
            }
            i = s.index(after: i)
        }
        
        return str.count == 0 ? String(s[s.index(before: s.endIndex)]) : str
    }
    
    func countPalindrome(s: String, start: String.Index, end: String.Index) -> Int {
        var startIndex = start
        var endIndex = end
        
        while startIndex <= endIndex {
            if s[s.index(after: startIndex)] != s[s.index(before: endIndex)] {
                return 0
            }
            
            startIndex = s.index(after: startIndex)
            endIndex = s.index(before: endIndex)
        }
        return s[start...end].count
    }
}
